package string;
import org.junit.Test;

import java.util.Stack;

public class ReverseWordsInString151 {
    @Test
    public void test() {
        reverseWords("the sky is blue");
        reverseWords("  hello world  ");
        reverseWords("a good   example");
        reverseWords("  Bob    Loves  Alice   ");
    }

    // [startIndex, endIndex)
    static class Range {
        int startIndex;
        int endIndex;

        public Range(int startIndex, int endIndex) {
            this.startIndex = startIndex;
            this.endIndex = endIndex;
        }
    }
    public String reverseWords(String s) {
        char[] c = s.toCharArray();
        Stack<Range> t = new Stack<>();
        int nextIndex = 0;
        while (nextIndex < s.length()) {
            if (c[nextIndex] == ' ') {
                nextIndex++;
            } else {
                nextIndex = readWord(c, nextIndex, t);
            }
        }

        StringBuilder sb = new StringBuilder();
        String sep = "";
        while (!t.isEmpty()) {
            Range r = t.pop();
            sb.append(sep);
            sb.append(c, r.startIndex, r.endIndex-r.startIndex);
            sep = " ";
        }
        System.out.format("s: %s, reversed: %s\n", s, sb.toString());
        return sb.toString();
    }

    public int readWord(char[] c, int startIndex, Stack<Range> t) {
        int i = startIndex;
        while (i < c.length && c[i] != ' ') {
            i++;
        }
        t.push(new Range(startIndex, i));
        return i;
    }
}
